package com.javase.algorithm.sort;

import java.util.Arrays;

/**
 *
 * @Description: 归并排序
 * @author: li yanhao
 * @eamil: liyanhao@timeforward.cn
 * @date:2022/6/24 12:45
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 1, 2, 5, 12};
        myMergeSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    private static void myMergeSort(int[] nums,int L,int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        myMergeSort(nums, L, mid);
        myMergeSort(nums, mid + 1, R);
        merge(nums, L, mid, R);
    }

    private static void merge(int[] nums, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M+1;
        while (p1 <= M && p2 <= R) {
            help[i++]= (nums[p1] <= nums[p2]) ? nums[p1++] : nums[p2++];
        }
        while (p1 <= M) {
            help[i++] = nums[p1++];
        }
        while (p2 <= R) {
            help[i++] = nums[p2++];
        }
        for ( i = 0; i < help.length; i++) {
            nums[L + i] = help[i];
        }
    }


}

















